//
//  Problem20.swift
//  LeetCode - 20 - 有效的括号
//
//  Created by 毕武侠 on 2020/7/4.
//  Copyright © 2020 毕武侠. All rights reserved.
//
/*
 【20 有效的括号】
 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

 有效字符串需满足：
 左括号必须用相同类型的右括号闭合。
 左括号必须以正确的顺序闭合。
 注意空字符串可被认为是有效字符串。

 示例 1:      输入: "()"            输出: true
 示例 2:      输入: "()[]{}"        输出: true
 示例 3:      输入: "(]"            输出: false
 示例 4:      输入: "([)]"          输出: false
 示例 5:      输入: "{[]}"          输出: true
 */
import UIKit

class Problem20: NSObject {
    func test() {
        let strLists = "()"
        print(strLists, " = ", isValid1(strLists))

        let strLists1 = "()[]{}"
        print(strLists1, " = ", isValid1(strLists1))


        let strLists2 = "(]"
        print(strLists2, " = ", isValid1(strLists2))

        let strLists3 = "([)]"
        print(strLists3, " = ", isValid1(strLists3))


        let strLists4 = "{[]}"
        print(strLists4, " = ", isValid1(strLists4))
        
        let strLists5 = "(([]){})"
        print(strLists5, " = ", isValid1(strLists5))
    }
    
    func isSym(_ c1: Character, _ c2: Character) -> Bool {
        return (c1 == "(" && c2 == ")") || (c1 == "[" && c2 == "]") || (c1 == "{" && c2 == "}");
    }
    
    // 简单的堆栈方法：
    // 依次把字符放进堆中，如果来了新字符和堆的最上面比较， 是一致的，就从堆中删除， 不是就加入
    func isValid(_ s: String) -> Bool {
        if s.count == 0 {
            return true
        } else if s.count == 1 {
            return false
        }
        
        var arrays: [Character] = []
        for (i, c) in s.enumerated() {
            if i == 0 {
                arrays.append(c)
            } else {
                if let first = arrays.last {
                    if self.isSym(first, c) == true {
                        _ = arrays.popLast()
                    } else {
                        arrays.append(c)
                    }
                } else {
                    arrays.append(c)
                }
            }
        }
        
        return arrays.count == 0
    }
    
    // 改进堆栈方法：
    // 如果是：([{， 入栈； 是：)]}, 判读最上面是否匹配，不匹配错误，匹配继续
    func isValid1(_ s: String) -> Bool {
        if s.count == 0 {
            return true
        } else if s.count == 1 {
            return false
        }
        
        var arrays: [Character] = []
        for c in s {
            if c == "(" || c == "[" || c == "{"  {
                arrays.append(c)
            } else {
                if let last = arrays.popLast() {
                    if self.isSym(last, c) == false {
                        return false
                    }
                } else {
                    return false
                }
            }
        }
        
        return arrays.count == 0
    }
}
